1. Field of the Invention
The invention relates to programming language compilers, and more specifically, to a method and apparatus for allocating registers via selective spilling.
2. Description of Related Art
An important function of an optimizing compiler is allocating physical registers to be used when code instructions generated by the optimizing compiler are executed. Physical registers are actual hardware registers supported by the particular platform on which the code instructions are executed. Ideally code instructions are executed in the available physical registers without requiring any additional physical registers. However, in many situations, the execution of code instructions requires more than the number of available physical registers. For example, the execution of a sequence of code instructions may require more intermediate values than the number of available physical registers. In these situations, the physical registers must be allocated to provide for the execution of the code instructions.
One approach for allocating physical registers used by contemporary optimizing compilers is a multi-pass approach. In one pass, data specified by processed code instructions is assigned to a set of virtual or "symbolic" registers which are sometimes considered to be infinite in number, but for practical reasons, arc usually limited to some fairly large number. During a subsequent pass, the set of virtual registers is assigned to a set of physical registers. For situations when the number of virtual registers is less than or equal to the number of physical registers, the contents of each of the virtual registers can be directly assigned to a physical register. However, when the number of virtual registers exceeds the number of physical registers, then the set of virtual registers must be mapped to the set of physical registers. In the context of compilers, mapping a set of virtual registers to a set of physical registers refers to determining an assignment of the set of virtual registers to the set of physical registers so that computations specified by a set of code instructions can be performed in the set of physical registers.
One approach for mapping a set of virtual registers to a set of physical registers is known as the graph coloring approach which is described in U.S. Pat. No. 4,571,678 issued to Chaitin on Feb. 18, 1986. Generally, the graph coloring approach involves constructing and analyzing a register interference graph for a set of code instructions. Each virtual register is represented in the register interference graph as a node. Two nodes are connected when the contents of two virtual registers represented by the nodes cannot simultaneously share a physical register at some point in time during the execution of the code instructions, effectively representing a conflict between the two nodes.
The register interference graph is then analyzed and nodes having fewer connections than the number of available physical registers are removed from the graph. If all of the nodes can be removed from the graph, then a coloring can be determined. That is, all of the virtual registers can be mapped to the available physical registers. However, sometimes the register interference graph contains one or more nodes having more connections to other nodes than the number of available physical registers. This means that the number of available physical registers is insufficient to store all of the intermediate values specified by the code instructions. Thus, some intermediate values must be stored in other memory.
The process of temporarily storing data from a physical register to another memory location is referred to as "spilling." Generally, spilling involves performing a spill operation, followed by one or more reload operations. The spill operation causes data contained in a physical register to be stored in another memory location, such as a runtime stack. Each reload operation causes the data to be loaded or copied from the other memory location into a physical register. Reload operations are performed when the data is required for a calculation.
In terms of the register interference graph, a spill is reflected in the graph by disconnecting a node from all other nodes in the graph. Then the graph is rebuilt and analyzed again. Any nodes that have been spilled have no connections to other nodes and are removed from the graph when the graph is analyzed. This process is repeated until a mapping of the set of virtual registers to the set of physical registers is determined.
The high level approach for mapping a set of virtual registers to a set of physical registers according to the graph coloring approach is illustrated by the flow chart of FIG. 1. After starting in step 100, a register interference graph is built in step 102. Then in step 104, the register interference graph is analyzed. As previously described, analyzing the register interference graph involves removing any nodes which have fewer connections to other nodes than the number of available physical registers.
In step 106, a determination is made as to whether the register interference graph can be colored. As previously discussed, if all of the nodes can be removed from the graph, indicating that there are no conflicts, then the graph can be colored. If so, then the process is complete in step 108. On the other hand, if in step 106 the graph cannot be colored, then in step 110, one of the virtual registers is spilled, which eliminates the spilled register as a conflicted node in the graph. In step 112 the register interference graph is rebuilt and then steps 104 through 112 are repeated until the register graph is colored.
The Problems
Although the spilling approach allows a set of virtual registers to be mapped to a set of physical registers, the approach does have some disadvantages. One disadvantage is that additional code instructions must be executed to perform the spill and reload operations. This increases the overall time required to process a sequence of code instructions which provides for the spilling of data. In addition, write and read operations to secondary storage media, such as runtime stacks, often take more time to execute than write and read operations to physical registers, such as Central Processing Unit (CPU) registers. Conventional spilling approaches add code instructions to perform a spill operation after data to be spilled is defined, and also add code instructions to perform a reload operation at each location in the code instructions where the data to be spilled is referenced. In many instances, this approach can result in a significant amount of extra code.
Consider the example illustrated by FIGS. 2A and 2B. A code block 200 includes code 202 which defines a variable X. Code block 200 also includes code 204, 206, 208 and 210, which use the variable X. Code block 200 may also include other code which is not illustrated.
FIG. 2B illustrates code block 200 which has been modified to reflect the spilling of the variable X. Specifically, code 212 has been added immediately following code 202, to perform a spill operation on the variable X. As previously discussed, the spill operation writes the variable X from a physical register to another memory location, such as a runtime stack.
In addition, code 214 has been added immediately before code 204 to perform a reload operation on the variable X, which causes the variable X to be reloaded into a physical register as X'. Code 204 then uses the reloaded variable X'. Similarly, code 216 has been added immediately before code 206 to reload the variable X as X", which is then used by code 206. Also, code 218 and 220 have also been added to reload the variable X as X'" and X"", respectively.
As is illustrated by code block 200 in FIG. 2B, performing spilling of variable X involves both writing the variable X from a physical register to another memory location (a spill operation), and also writing the variable X from the memory location into a physical register (a reload operation) for each occurrence of variable X in code block 200. Conventional spill algorithms do not discriminate as to where the additional code to perform the reload operations is added. Rather, the code instructions for performing the reload operations is added prior to each and every use of the spill variable. This can adversely affect performance when a reload operation is added to a portion of code instructions which is repeated many times, such as a loop. Also, a physical register conflict may only occur at one location in a code block and yet, according to conventional approaches, code to perform a reload operation is added at every use of the spill variable.
In view of the need for spilling virtual registers to provide for the mapping of a set of virtual registers to a set of physical registers, and the limitations in the prior approaches, there is a need for an approach for allocating a set of virtual registers to a set of physical registers that uses a more efficient approach for register spilling.